package com.leetcode.根据数据结构分类.链表;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2021/3/2
 * @description: 160. 相交链表
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 */
public class A_160_相交链表 {
	public static void main(String[] args) {

	}

	/**
	 * 这道题如果不要求 O(1) 的空间，可以用 hashMap 来存一个链表的所有节点，然后再遍历
	 * 另一个链表，直到找到重复的引用节点。
	 * --
	 * 但是既然对空间要求了，这道题就有些脑筋急转弯了。
	 * 【最多遍历两遍：使用双指针，分别遍历两个链表；
	 * 如果一个链表遍历结束立刻将指针移动到另一个链表的头部，继续遍历】
	 *
	 * @param headA
	 * @param headB
	 * @return
	 */
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		if (headA == null || headB == null) {
			return null;
		}
		ListNode p1 = headA;
		ListNode p2 = headB;
		//统计到达结尾的次数
		int count = 0;
		//还是先遍历一次吧
		while (count < 2) {
			if (p1 == p2) {
				//如果引用相同，说明本节点就是相交的节点
				return p1;
			}
			//处理 p1 节点
			if (p1.next == null) {
				//如果p1 已经遍历到结尾了
				//将 p1 指向 第二个链表
				p1 = headB;
				count++;
			} else {
				p1 = p1.next;
			}

			//同理处理 p2 节点
			if (p2.next == null) {
				p2 = headA;
				count++;
			} else {
				p2 = p2.next;
			}
		}
		//再进行一次遍历
		while (true) {
			if (p1 == p2) {
				return p1;
			}
			if (p1.next == null) {
				break;
			} else {
				p1 = p1.next;
			}

			if (p2.next == null) {
				count++;
			} else {
				p2 = p2.next;
			}
		}

		return null;
	}
}
